#pragma once

#include <iostream>
#include <vector>

const int N = 1e6;
int temp[N];

void merge_sort(std::vector<int>& nums, int left, int right)
{
	if (left >= right) return;

	int mid = left + right >> 1;
	merge_sort(nums, left, mid), merge_sort(nums, mid + 1, right);

	int i = left, j = mid + 1, k = 0;
	while (i <= mid && j <= right)
	{
		if (nums[i] < nums[j]) temp[k++] = nums[i++];
		else temp[k++] = nums[j++];
	}
	while (i <= mid) temp[k++] = nums[i++];
	while (j <= right) temp[k++] = nums[j++];

	for (int i = left, k = 0; i <= right;) nums[i++] = temp[k++];
}
